COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{F1F2F3⊂C<NαWINGED EDGE.λ30P1I125,0JCFA}
C00004 00003	{F1F2F3⊂C<NαWINGED EDGE.λ30P13JUFA}
C00011 00004		An example  of a purely  descriptive vision technique  is the
C00016 ENDMK
C⊗;
{F1;F2;F3;⊂C;<N;αWINGED EDGE.;λ30;P1;I125,0;JC;FA}
{JC;FD} A POLYHEDRON REPRESENTATION FOR COMPUTER VISION
{λ15;FA} Author: {JCFC} Bruce G. Baumgart
{FA} Author's Address: {JC} Stanford Artificial Intelligence Laboratory
{JC} Stanford University
{JC} Stanford, California 94305

{JC} for the National Computer Conference
{JC} Session on Graphic Models of Physical Systems
{JC} Session chaired by Charles M. Eastman

{λ10;W250;JA;FA}
	1.	Use of Polyhedra in Computer Vision.
	2.	Introduction to the Winged Edge.
	3.	Sequential Accessing.
	4.	Perimeter Accessing.
	5.	Basic Polyhedron Synthesis.
	6.	Edge and Face Splitting.
	7.	References.

{λ30;W0;I1000,0;JU}
{F1;F2;F3;⊂C;<N;αWINGED EDGE.;λ30;P13;JUFA}

⊂1.	Use of Polyhedra in Computer Vision.⊃

	My  approach to  computer  vision  is best  characterized  as
inverse  computer  graphics.   In  computer  graphics,  the world  is
represented in sufficient  detail so that  the image forming  process
can be numerically simulated to generate synthetic television images;
in the inverse, perceived television pictures (from a real TV camera)
are analysed to compute  detailed geometric models. For  example, the
polyhedron in Figure 1 was  computed from views of a plastic horse on
a turntable. It is hoped, that visually acquired 3-D geometric models
can  be of  use  to other  robotic  processes such  as  manipulation,
navigation or recognition. 

	Once  acquired, a  3-D model  can be  used to  anticipate the
appearance of an  object in a scene,  making feasible a  quantitative
form of  visual feedback.  In Figure 2  for example,  the approximate
video  appearance of  the machine parts  schematically depicted (top)
can be computed and analyzed for edges (middle) and  compared with an
edge anaylsis  of an  actual video image  of the parts  (bottom).  By
comparing  the   predicted  image   with  a   perceived  image,   the
correspondence between features of the internal model and features of
the external  reality can be established and  a corrected location of
the parts and the camera can be measured. 
	An example  of a purely  descriptive vision technique  is the
silhouette  cone intersection method, which  is a conceptually simple
form of wide angle  stereo reconstruction. The  idea arose out of  an
original intention  to do  "blob" oriented visual  model acquisition,
however a 2-D blob came to be represented by a silhouette polygon and
a 3-D blob consequently came  to be represented by a  polyhedron. The
present  implementation requires  a very  favorably  arranged viewing
environment (white  objects  on  dark  backgrounds  or  vice  versa);
application  to more  natural  situations might  be  possible if  the
necessary hardware (and software) were available for extracting depth
discontinuities by bulk correlation.  Furthermore, the restriction to
turntable  rotation is  for the  sake  of easy  camera solving;  this
restriction  could be  lifted by providing  stronger feature tracking
for camera calibration. 

	Like in  the  joke about  carving a  statue  by cutting  away
everything that does not look like the subject, the approximate shape
of the horse  is hewed out  of 3-D space  by cutting away  everything
that falls outside of the silhouettes. The example of silhouette cone
intersection depicted in Figure 1; the  model was made from three
silhouettes of the  horse facing to  the left  which may be  compared
with a video image and a final view of the result of the horse facing
to  the right -  a backside consistent with the front views
was automatically constructed by the process.

	The silhouette cone intersection method can construct concave
objects and  even objects with  holes in them  - what are  missed are
concavities with a  full rim, that  is points on  the surface of  the
object whose tangent plane  cuts the surface in a  loop that encloses
the point. 

	Unfortunately, the above  approachs to computer  vision (both
verification vision and descriptive vision) are only as strong as the
state of the  art in 3-D  computer graphics. Accordingly my  recent vision
work has  almost entirely been a  quest for better ways  to represent
and  manipulate 3-D objects.  Restricting the problem to  representing
solid,  opaque, rigid  3-D  objects  only a  very  few  significantly
different  geometric  modeling  ideas  are known:  arrays,  3-D
density functions, 2-D parametric  functions, volume elements,  cross
sectional elements,  skeltons, manifolds  and polyhedra;  of which  I
have  concentrated on  polyhedra because  they  are simple  enough to
readily handle  in a  computer  and complex  enough to  represent  an
arbitrary  opaque surface.   Accordingly  the rest  of this  paper  is
devoted  to  presenting  a particular  polyhedron  representation for
which convenient sets of manipulation routines have been developed.